Group shifted strings

Time: O(NLogN); Space: O(N); easy

Given a string, we can “shift” each of its letter to its successive letter.

For example: “abc” -> “bcd”.

We can keep “shifting” which forms the sequence: “abc” -> “bcd” -> … -> “xyz”

Given a list of strings which contains only lowercase alphabets,

group all strings that belong to the same shifting sequence.

Example 1:

Input: strings = [“abc”, “bcd”, “acef”, “xyz”, “az”, “ba”, “a”, “z”]

Output:

[
  ["abc", "bcd", "xyz"],
  ["az", "ba"],
  ["acef"],
  ["a", "z"]
]

Note:

  • For the return value, each inner list’s elements must follow the lexicographic order.

[17]:

import collections

class Solution1(object):
    """
    Time: O(NLogN)
    Space: O(N)
    """
    def groupStrings(self, strings):
        """
        :type strings: List[str]
        :rtype: List[List[str]]
        """
        groups = collections.defaultdict(list)

        # Grouping
        for s in strings:
            groups[self.hashStr(s)].append(s)

        result = []
        for key, val in groups.items():     # key = 'abc', val = ['abc', 'bcd', 'xyz']
            # print(key, val)
            result.append(sorted(val))

        return result

    def hashStr(self, s):
        base = ord(s[0][0])
        hashcode = ''
        for i in range(len(s)):
            if ord(s[i][0]) - base >= 0:
                hashcode += chr(ord('a') + ord(s[i][0]) - base)
            else:
                hashcode += chr(ord('a') + ord(s[i][0]) - base + 26)
        # print(hashcode)
        return hashcode

[18]:

s = Solution1()
strings = ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"]
# print(s.groupStrings(strings))
assert s.groupStrings(strings) == [
  ["abc", "bcd", "xyz"],
  ["acef"],
  ["az", "ba"],
  ["a", "z"]
]